Search Results

Documents authored by Goaoc, Xavier

Document
Complete Volume
DOI: 10.4230/LIPIcs.SoCG.2022
LIPIcs, Volume 224, SoCG 2022, Complete Volume

Authors: Xavier Goaoc and Michael Kerber

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
LIPIcs, Volume 224, SoCG 2022, Complete Volume
Cite as

38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 1-1110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Proceedings{goaoc_et_al:LIPIcs.SoCG.2022,
  title =	{{LIPIcs, Volume 224, SoCG 2022, Complete Volume}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{1--1110},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022},
  URN =		{urn:nbn:de:0030-drops-160075},
  doi =		{10.4230/LIPIcs.SoCG.2022},
  annote =	{Keywords: LIPIcs, Volume 224, SoCG 2022, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SoCG.2022.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Xavier Goaoc and Michael Kerber

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SoCG.2022.0,
  author =	{Goaoc, Xavier and Kerber, Michael},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.0},
  URN =		{urn:nbn:de:0030-drops-160087},
  doi =		{10.4230/LIPIcs.SoCG.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.40
A Stepping-Up Lemma for Topological Set Systems

Authors: Xavier Goaoc, Andreas F. Holmsen, and Zuzana Patáková

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Intersection patterns of convex sets in ℝ^d have the remarkable property that for d+1 ≤ k ≤ 𝓁, in any sufficiently large family of convex sets in ℝ^d, if a constant fraction of the k-element subfamilies have nonempty intersection, then a constant fraction of the 𝓁-element subfamilies must also have nonempty intersection. Here, we prove that a similar phenomenon holds for any topological set system ℱ in ℝ^d. Quantitatively, our bounds depend on how complicated the intersection of 𝓁 elements of ℱ can be, as measured by the maximum of the ⌈d/2⌉ first Betti numbers. As an application, we improve the fractional Helly number of set systems with bounded topological complexity due to the third author, from a Ramsey number down to d+1. We also shed some light on a conjecture of Kalai and Meshulam on intersection patterns of sets with bounded homological VC dimension. A key ingredient in our proof is the use of the stair convexity of Bukh, Matoušek and Nivasch to recast a simplicial complex as a homological minor of a cubical complex.
Cite as

Xavier Goaoc, Andreas F. Holmsen, and Zuzana Patáková. A Stepping-Up Lemma for Topological Set Systems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SoCG.2021.40,
  author =	{Goaoc, Xavier and Holmsen, Andreas F. and Pat\'{a}kov\'{a}, Zuzana},
  title =	{{A Stepping-Up Lemma for Topological Set Systems}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.40},
  URN =		{urn:nbn:de:0030-drops-138396},
  doi =		{10.4230/LIPIcs.SoCG.2021.40},
  annote =	{Keywords: Helly-type theorem, Topological combinatorics, Homological minors, Stair convexity, Cubical complexes, Homological VC dimension, Ramsey-type theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.49
Convex Hulls of Random Order Types

Authors: Xavier Goaoc and Emo Welzl

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We establish the following two main results on order types of points in general position in the plane (realizable simple planar order types, realizable uniform acyclic oriented matroids of rank 3): (a) The number of extreme points in an n-point order type, chosen uniformly at random from all such order types, is on average 4+o(1). For labeled order types, this number has average 4-8/(n^2 - n +2) and variance at most 3. (b) The (labeled) order types read off a set of n points sampled independently from the uniform measure on a convex planar domain, smooth or polygonal, or from a Gaussian distribution are concentrated, i.e., such sampling typically encounters only a vanishingly small fraction of all order types of the given size. Result (a) generalizes to arbitrary dimension d for labeled order types with the average number of extreme points 2d+o(1) and constant variance. We also discuss to what extent our methods generalize to the abstract setting of uniform acyclic oriented matroids. Moreover, our methods allow to show the following relative of the Erdős-Szekeres theorem: for any fixed k, as n → ∞, a proportion 1 - O(1/n) of the n-point simple order types contain a triangle enclosing a convex k-chain over an edge. For the unlabeled case in (a), we prove that for any antipodal, finite subset of the 2-dimensional sphere, the group of orientation preserving bijections is cyclic, dihedral or one of A₄, S₄ or A₅ (and each case is possible). These are the finite subgroups of SO(3) and our proof follows the lines of their characterization by Felix Klein.
Cite as

Xavier Goaoc and Emo Welzl. Convex Hulls of Random Order Types. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SoCG.2020.49,
  author =	{Goaoc, Xavier and Welzl, Emo},
  title =	{{Convex Hulls of Random Order Types}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.49},
  URN =		{urn:nbn:de:0030-drops-122074},
  doi =		{10.4230/LIPIcs.SoCG.2020.49},
  annote =	{Keywords: order type, oriented matroid, Sylvester’s Four-Point Problem, random convex hull, projective plane, excluded pattern, Hadwiger’s transversal theorem, hairy ball theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.40
An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting

Authors: Xavier Goaoc, Andreas Holmsen, and Cyril Nicaud

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We study the problem of deciding if a given triple of permutations can be realized as geometric permutations of disjoint convex sets in R^3. We show that this question, which is equivalent to deciding the emptiness of certain semi-algebraic sets bounded by cubic polynomials, can be "lifted" to a purely combinatorial problem. We propose an effective algorithm for that problem, and use it to gain new insights into the structure of geometric permutations.
Cite as

Xavier Goaoc, Andreas Holmsen, and Cyril Nicaud. An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SoCG.2019.40,
  author =	{Goaoc, Xavier and Holmsen, Andreas and Nicaud, Cyril},
  title =	{{An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.40},
  URN =		{urn:nbn:de:0030-drops-104442},
  doi =		{10.4230/LIPIcs.SoCG.2019.40},
  annote =	{Keywords: Geometric permutation, Emptiness testing of semi-algebraic sets, Computer-aided proof}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.17
Consistent Sets of Lines with no Colorful Incidence

Authors: Boris Bukh, Xavier Goaoc, Alfredo Hubard, and Matthew Trager

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We consider incidences among colored sets of lines in {R}^d and examine whether the existence of certain concurrences between lines of k colors force the existence of at least one concurrence between lines of k+1 colors. This question is relevant for problems in 3D reconstruction in computer vision.
Cite as

Boris Bukh, Xavier Goaoc, Alfredo Hubard, and Matthew Trager. Consistent Sets of Lines with no Colorful Incidence. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bukh_et_al:LIPIcs.SoCG.2018.17,
  author =	{Bukh, Boris and Goaoc, Xavier and Hubard, Alfredo and Trager, Matthew},
  title =	{{Consistent Sets of Lines with no Colorful Incidence}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.17},
  URN =		{urn:nbn:de:0030-drops-87308},
  doi =		{10.4230/LIPIcs.SoCG.2018.17},
  annote =	{Keywords: Incidence geometry, image consistency, probabilistic construction, algebraic construction, projective configuration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.41
Shellability is NP-Complete

Authors: Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We prove that for every d >= 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d >= 2 and k >= 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d >= 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes.
Cite as

Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. Shellability is NP-Complete. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SoCG.2018.41,
  author =	{Goaoc, Xavier and Pat\'{a}k, Pavel and Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli},
  title =	{{Shellability is NP-Complete}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{41:1--41:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.41},
  URN =		{urn:nbn:de:0030-drops-87542},
  doi =		{10.4230/LIPIcs.SoCG.2018.41},
  annote =	{Keywords: Shellability, simplicial complexes, NP-completeness, collapsibility}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.10
The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Authors: Boris Aronov, Otfried Cheong, Michael Gene Dobbins, and Xavier Goaoc

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We show that the union of translates of a convex body in three dimensional space can have a cubic number holes in the worst case, where a hole in a set is a connected component of its compliment. This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions.
Cite as

Boris Aronov, Otfried Cheong, Michael Gene Dobbins, and Xavier Goaoc. The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2016.10,
  author =	{Aronov, Boris and Cheong, Otfried and Dobbins, Michael Gene and Goaoc, Xavier},
  title =	{{The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.10},
  URN =		{urn:nbn:de:0030-drops-59024},
  doi =		{10.4230/LIPIcs.SoCG.2016.10},
  annote =	{Keywords: Union complexity, Convex sets, Motion planning}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.224
On the Smoothed Complexity of Convex Hulls

Authors: Olivier Devillers, Marc Glisse, Xavier Goaoc, and Rémy Thomasse

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We establish an upper bound on the smoothed complexity of convex hulls in R^d under uniform Euclidean (L^2) noise. Specifically, let {p_1^*, p_2^*, ..., p_n^*} be an arbitrary set of n points in the unit ball in R^d and let p_i = p_i^* + x_i, where x_1, x_2, ..., x_n are chosen independently from the unit ball of radius r. We show that the expected complexity, measured as the number of faces of all dimensions, of the convex hull of {p_1, p_2, ..., p_n} is O(n^{2-4/(d+1)} (1+1/r)^{d-1}); the magnitude r of the noise may vary with n. For d=2 this bound improves to O(n^{2/3} (1+r^{-2/3})). We also analyze the expected complexity of the convex hull of L^2 and Gaussian perturbations of a nice sample of a sphere, giving a lower-bound for the smoothed complexity. We identify the different regimes in terms of the scale, as a function of n, and show that as the magnitude of the noise increases, that complexity varies monotonically for Gaussian noise but non-monotonically for L^2 noise.
Cite as

Olivier Devillers, Marc Glisse, Xavier Goaoc, and Rémy Thomasse. On the Smoothed Complexity of Convex Hulls. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 224-239, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{devillers_et_al:LIPIcs.SOCG.2015.224,
  author =	{Devillers, Olivier and Glisse, Marc and Goaoc, Xavier and Thomasse, R\'{e}my},
  title =	{{On the Smoothed Complexity of Convex Hulls}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{224--239},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.224},
  URN =		{urn:nbn:de:0030-drops-51451},
  doi =		{10.4230/LIPIcs.SOCG.2015.224},
  annote =	{Keywords: Probabilistic analysis, Worst-case analysis, Gaussian noise}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.300
Limits of Order Types

Authors: Xavier Goaoc, Alfredo Hubard, Rémi de Joannis de Verclos, Jean-Sébastien Sereni, and Jan Volec

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
The notion of limits of dense graphs was invented, among other reasons, to attack problems in extremal graph theory. It is straightforward to define limits of order types in analogy with limits of graphs, and this paper examines how to adapt to this setting two approaches developed to study limits of dense graphs. We first consider flag algebras, which were used to open various questions on graphs to mechanical solving via semidefinite programming. We define flag algebras of order types, and use them to obtain, via the semidefinite method, new lower bounds on the density of 5- or 6-tuples in convex position in arbitrary point sets, as well as some inequalities expressing the difficulty of sampling order types uniformly. We next consider graphons, a representation of limits of dense graphs that enable their study by continuous probabilistic or analytic methods. We investigate how planar measures fare as a candidate analogue of graphons for limits of order types. We show that the map sending a measure to its associated limit is continuous and, if restricted to uniform measures on compact convex sets, a homeomorphism. We prove, however, that this map is not surjective. Finally, we examine a limit of order types similar to classical constructions in combinatorial geometry (Erdos-Szekeres, Horton...) and show that it cannot be represented by any somewhere regular measure; we analyze this example via an analogue of Sylvester's problem on the probability that k random points are in convex position.
Cite as

Xavier Goaoc, Alfredo Hubard, Rémi de Joannis de Verclos, Jean-Sébastien Sereni, and Jan Volec. Limits of Order Types. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 300-314, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SOCG.2015.300,
  author =	{Goaoc, Xavier and Hubard, Alfredo and de Joannis de Verclos, R\'{e}mi and Sereni, Jean-S\'{e}bastien and Volec, Jan},
  title =	{{Limits of Order Types}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{300--314},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.300},
  URN =		{urn:nbn:de:0030-drops-51264},
  doi =		{10.4230/LIPIcs.SOCG.2015.300},
  annote =	{Keywords: order types, Limits of discrete structures, Flag algebras, Erdos-Szekeres, Sylvester’s problem}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.476
On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result

Authors: Xavier Goaoc, Isaac Mabillard, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2. Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem. In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.
Cite as

Xavier Goaoc, Isaac Mabillard, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 476-490, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SOCG.2015.476,
  author =	{Goaoc, Xavier and Mabillard, Isaac and Pat\'{a}k, Pavel and Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli},
  title =	{{On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{476--490},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.476},
  URN =		{urn:nbn:de:0030-drops-51256},
  doi =		{10.4230/LIPIcs.SOCG.2015.476},
  annote =	{Keywords: Heawood Inequality, Embeddings, Van Kampen–Flores, Manifolds}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.507
Bounding Helly Numbers via Betti Numbers

Authors: Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest.
Cite as

Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. Bounding Helly Numbers via Betti Numbers. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 507-521, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SOCG.2015.507,
  author =	{Goaoc, Xavier and Pat\'{a}k, Pavel and Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli},
  title =	{{Bounding Helly Numbers via Betti Numbers}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{507--521},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.507},
  URN =		{urn:nbn:de:0030-drops-51297},
  doi =		{10.4230/LIPIcs.SOCG.2015.507},
  annote =	{Keywords: Helly-type theorem, Ramsey’s theorem, Embedding of simplicial complexes, Homological almost-embedding, Betti numbers}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact